/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.string;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import org.junit.Test;

/**
 * <p>
 * 判断字符串是否可以被分词
 *  输入 s = "leetcode", 
 *  dict = ["leet", "code"].
 * 
 *  返回true
 *   "leetcode" can be segmented as "leet code".
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月14日
 */
public class WordBreak {

    public boolean wordBreak(String s, Set<String> wordDict) {
        Map<String,Boolean> memorized = new HashMap<>();
        return wordBreak(s,wordDict,memorized);
    }

    /**
     *  单词分割
     * @param s
     * @param wordDict
     * @param memorized
     * @return
     * @author towan
     * 2015年6月14日
     */
    private boolean wordBreak(String s, Set<String> wordDict, Map<String, Boolean> memorized) {
        boolean result = false;
        if(s==null || s.length()==0){
            return result;
        }
        if(wordDict.contains(s)){
            return true;
        }
        if(memorized.containsKey(s)){
            return memorized.get(s);
        }
        int len = s.length();
        for(int i=0;i<len ;i++){
            String prefix = s.substring(0, i);
            if(wordDict.contains(prefix)){
                //这个前缀是一个单词，递归调用函数
                if(wordBreak(s.substring(i, len), wordDict, memorized)){
                    return true;
                }
            }
        }
        memorized.put(s, false);
        return result;
    }
    @Test
    public void test(){
        String s = "leetcode";
        Set<String> dict = new HashSet<String>();
        dict.add("leet");
        dict.add("code");
        boolean wordBreak = wordBreak(s, dict);
        System.out.println(wordBreak);
        String s2= "leetcode22";
        System.out.println( wordBreak(s2, dict));
    }
    @Test
    public void testExcellTime(){
        String str = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        Set<String> dict = new HashSet<>();
        String s = "";
        for(int i=0;i<10;i++){
            s+="a";
            dict.add(s);
        }
        System.out.println(dict);
        long start = System.currentTimeMillis();
        boolean wordBreak = wordBreak(str, dict);
        long end = System.currentTimeMillis();
        System.out.println(wordBreak+" use time:"+(end-start)+"ms");
    }
}
